package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-25 18:23
 */
public class 题库_0055_跳跃游戏 {

  static
  class Solution {
    public boolean canJump(int[] nums) {
//      return backtrack(nums, 0);
      if (nums == null || nums.length < 2) {
        return true;
      }

      int max = nums[0];
      for (int i = 1; i < nums.length; ++i) {
        if (i > max) {
          return false;
        }
        if (max >= nums.length - 1) {
          return true;
        }
        max = Math.max(max, i + nums[i]);
      }

      return true;
    }

    private boolean backtrack(int[] nums, int index) {
      if (index == nums.length - 1) {
        return true;
      }
      for (int i = 1; i <= nums[index]; ++i) {
        if (backtrack(nums, index + i)) {
          return true;
        }
      }
      return false;
    }
  }

}
